package _01_sort;

import java.util.Arrays;

/**
 * @author: mornd
 * @dateTime: 2023/5/21 - 16:42
 * 插入排序，将数组分为未排序和已排序两区域，从未排序区添加元素到已排序区的指定位置
 * 初始时，将第一个元素视为已排序序列，然后从第二个元素开始，逐个将未排序的元素插入到已排序序列的合适位置，直到所有元素都被插入。
 * 2,4,1
 * 2,4,4
 * 2,2,4
 * 1,2,4
 */
public class InsertionSort {
    public static void main(String[] args) {
        int[] arr = {9, 2, 17, 3, 7, 5, 13, 18};
        insertion(arr);
        System.out.println(Arrays.toString(arr));
    }

    //    private static void insertion(int[] arr) {
//        for (int i = 1; i < arr.length; i++) {
//            int t = arr[i];
//            int j = i - 1;
//            while (j >= 0) {
//                if(t < arr[j]) {
//                    arr[j + 1] = arr[j];
//                } else {
//                    break;
//                }
//                j--;
//            }
//            arr[j+1] = t;
//        }
//    }

    private static void insertion(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int t = arr[i];
            int j = i - 1;
            for (; j >= 0 && arr[j] > t; j--) {
                arr[j + 1] = arr[j];
            }

            if (j != i - 1) {
                arr[j + 1] = t;
            }
        }
    }
}
